  /*
** Danny newman
   Erik Rotaru
   Aaron Hill
   4/15/10
   Project 3 CS457
   
   Myresolver
*/

#include <stdio.h>
#include <stdlib.h>
#include <cstdlib>
#include <unistd.h>
#include <errno.h>
#include <netdb.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include<iostream>
#include <arpa/inet.h>
#include <string.h>


static int debug = 0;
static int printResponseByteArray = 0;
static int nameDebug = 0;

#define MAXDATASIZE 100 // max number of bytes we can get at once
typedef unsigned char byte;
using namespace std;

/** struct declarations **/
struct data_msg;
struct DNS_header;

struct ServerList{
	char ** servers;
	int numServers;
	int currServer;
	bool isIPFormat[100];
};

struct RRSIG_Record{
	short Type;
	byte algorithm;
	byte labels;
	int Orig_TTL;
	int sig_Expiration;
	int sig_Inception;
	unsigned short keytag;
	char * signature;
	char * sigCalc;
};
struct ResourceRecord{
	char * Name;
	short TYPE, CLASS;
	int TTL;
	unsigned short RDLENGTH;
	char * RDATA;
	short PREFERENCE;
	RRSIG_Record * RRSIG;
};

/** function declarations *************************************/
int queryDNS(char * hostname, short Qtype, ResourceRecord * rRecord);
void *get_in_addr(struct sockaddr *sa);
void lookupZoneInfo(char * zonename);
int createDNSQueryMessage(byte * byteArray, char *hostname, short Qtype);
int constructDNSRR(byte * byteArray, int offset); 
int constructDNSQuestion(byte * byteArray, char * hostname, short Qtype);
void constructDNSHeader(byte * byteArray, DNS_header * head);
void getDNSServers(ServerList * sl);
int parseResponseMessage(byte * byteArray, int offset, ServerList *sl, char * currKnown, char *hostname, ResourceRecord *rRecord);
int parseResourceRecord(byte * responseMessage, int offset, ResourceRecord * rRecord);
int parseName(byte * responseMessage, int offset, ResourceRecord * rRecord, char type, char * theName);
void parseRRSIG(byte * byteArray, int offset, RRSIG_Record *rrsig, int totalSize);
void printRRList(ResourceRecord * rRecord, int size);
void updateServerList(ServerList * serverList, ResourceRecord * authority, int numAuthority, ResourceRecord * additional, int numAdditional);
int compareBestKnown(char * currKnown, char*hostname, ResourceRecord * authority, int numAuthority);
void shiftLeft(ResourceRecord * rList, int numList, int offset);
void toLowerCase(char * string);
/** ***********************************************************/



/** structs to hold message information */
// THE DATA MESSAGE : it contains a version & Data.
struct data_msg {		 //
	char version; 		 //  -  1 byte (char) of Version data
	unsigned int data;       //  -  Unsigned 32 bit number (unsigned int) passed via a Client
}__attribute__((__packed__));	 //  -  PACKED. So its as small as possible w/ respect to its bits.

struct DNS_header {
	short ID;
	short QR;
	short OPCODE;
	short AA;
	short TC;
	short RD;
	short RA;
	short Z;
	short RCODE;
	short QDCOUNT;
	short ANCOUNT;
	short NSCOUNT;
	short ARCOUNT;
};

// get sockaddr, IPv4 or IPv6:
void *get_in_addr(struct sockaddr *sa)
{
    if (sa->sa_family == AF_INET) {  // if the type is IPV4
        return &(((struct sockaddr_in*)sa)->sin_addr); //return this
    }
    return &(((struct sockaddr_in6*)sa)->sin6_addr); // (Implied) ELSE: its Ipv6
}


/** inserts the header information found in head, into the
    the first 12 bytes of the byteArray */
void constructDNSHeader(byte * byteArray, DNS_header * head){
	//bits 0 to 15, ID
	byteArray[0] = (0xFF00 & head->ID) >> 8;
	byteArray[1] = 0x00FF & head->ID;

	//bits 16-23 = QR, Opcode, AA, TC, RD
	//short dub_octet = 0x0000;
	//octet = (0x7800 & (head->OPCODE << 4));
	//printf("first octet: %#x\n",octet);
	byteArray[2] = 0x00;
	
	//bits 24-31 =  RA, Z, RCODE
	byteArray[3] = 0x00;
	
	//bits 32-47, QDCOUNT
	byteArray[4] = (0xFF00 & head->QDCOUNT) >> 8;
	byteArray[5] = 0x00FF & head->QDCOUNT;
	
	//bits 48-95
	byteArray[6] = 0x00;
	byteArray[7] = 0x00; //ANCOUNT
	
	byteArray[8] = 0x00;
	byteArray[9] = 0x00; //NSCOUNT
	
	byteArray[10] = 0x00;
	byteArray[11] = 0x00; //ARCOUNT, 1 for RRSIG
}

/** inserts the question information, which is the MX record
	for the given hostname into the byteArray starting after the
	the header section, byte 13. returns the total length of the question section */
int constructDNSQuestion(byte * byteArray, char * hostname, short Qtype){
	byte domainLength[4]; //lengths of the different parts of the domain name
	int num = 0; //num is the domain number we are currently finding the length of
	int count = 0; //count is the number of characters counted between the '.' s
	
	//find the '.' between each part of domain name eg www.google.com and associate
	//each part with a length stored in domainLength
	for(unsigned int i=0;i<strlen(hostname);i++){
		if(hostname[i] == '.'){
			domainLength[num++] = (byte)count;
			count = 0;
		}
		else
			count++;
	}
	if(count > 0){
		domainLength[num++] = count;
	}
		
	int offset = 12; //offset is the current position in the bytearray starting right after the header section
	int hostOffset = 0; // hostOffset is the offset in the hostname where we are currently reading chars from
	int totalSize = 0; //total size is the current total number of octets in the question section
	
	//insert each label of the domain name into the byteArray
	//a label is an octet for length followed by that number of octets
	//with ascii characters and the last label is followed by a 0 octet for the root
	for(int i=0;i<num;i++){
		byteArray[offset++] = domainLength[i];
		totalSize += domainLength[i] + 1;
		for(int index=0;index<domainLength[i];index++){
			byteArray[offset++] = (byte)hostname[index + hostOffset];
		}
		hostOffset += domainLength[i]+1;
	}
	
	byteArray[offset++] = 0x00; //the 0 octet for the root
	
	//The QTYPE for MX (mail exchange) is 15, QTYPE A is IPv4 address
	byteArray[offset++] = 0xFF & Qtype>>8;
	byteArray[offset++] = 0xFF & Qtype;
	//The QCLASS for IN (internet) is 1
	byteArray[offset++] = 0x00;
	byteArray[offset] = 0x01;
	
	totalSize += 5; // add 5 for 0 octet, QTYPE and QCLASS
	
	return totalSize;
}

int constructDNSRR(byte * byteArray, int offset) {
	byteArray[11] = 0x01; //set the additional section to 1 in header
	byteArray[offset++] = 0x00;//root for end of domain name
	byteArray[offset++] = 0x00;//type = 41	
	byteArray[offset++] = 0x29; //Type = 41
	byteArray[offset++] = 0x00; //Class = 1 for IN
	byteArray[offset++] = 0x01; //Class = 1 for IN
	byteArray[offset++] = 0x00; //TTL: Extended RCode = 0; Version = 0
	byteArray[offset++] = 0x00; //TTL: Extended RCode = 0; Version = 0
	byteArray[offset++] = 0x80; //DO bit is set to 1
	byteArray[offset++] = 0x00; //Rest of Z is 0
	byteArray[offset++] = 0x00; //RDLength = 6 octets
	byteArray[offset++] = 0x00; //RData: Option Code = 41

	return offset;
}


/** constructs the DNS Query message and returns the total number of octets in
	the message */
int createDNSQueryMessage(byte * byteArray, char * hostname, short Qtype){
	DNS_header *head = new DNS_header();	
	head->ID = 5385;
	head->OPCODE = 0;
	head->QDCOUNT = 1;
	
	constructDNSHeader(byteArray, head);
	int questionLength = constructDNSQuestion(byteArray, hostname, Qtype);
	//print question
	if(debug){
		printf("Header Section:\n");
		for(int i=0;i<questionLength+12;i++){
			if(i==12)printf("\nQuestion Section:\n");
			printf("byte %d: %#x\n",i,byteArray[i]);
		}
	}
	return questionLength + 12;
}


/** open a connection with the DNS 
	iteratively and request Info **/

int queryDNS(char * hostname, short Qtype, ResourceRecord * rRecord){
	int sockfd;
	int numbytes; //number bytes received/sent
	fd_set readset; //file descriptor ready to read
	struct addrinfo hints, *servinfo, *p;
	int rv;
	struct timeval tv; //struct holding microseconds and seconds for timeout with select
	tv.tv_sec = 3; //seconds
	tv.tv_usec = 0; //microseconds
    
	byte byteArray[512];
	char * server;
	char port[] = "53";
	char *currKnown = new char[256];
	currKnown[0] = '.'; //this is the closest known match to the zonename, '.' is the root servers
	currKnown[1] = '\0';
	ServerList *serverList = new ServerList();
	serverList->currServer = 0;
	getDNSServers(serverList);
	
	//creates a DNS query message as a byteArray
	int messageSize = createDNSQueryMessage(byteArray, hostname, Qtype);
	int rrsigSize = constructDNSRR(byteArray, messageSize);
	if(debug){
		for(int i=0;i<serverList->numServers;i++){
			printf("root server %s\n",serverList->servers[i]);
		}
	}
	
	bool firstTry = true;
	// big while loop to run through all servers currently in the list and query with byteArray message
   	while(serverList->currServer < serverList->numServers){
 		//if firstTry is true then set the current server to the first server from current position that is in IPv4
 		//if firstTry is false set it to non IPv4 addresses
 		for(;serverList->currServer < serverList->numServers;  serverList->currServer++){
 			if(serverList->isIPFormat[serverList->currServer] == firstTry){
 				if(!firstTry){//if not in IPv4 then query all servers for IPv4 address for this server
		 			ResourceRecord * rRecord = new ResourceRecord[20];
					//Qtype 1 == A
					int numAnswers = queryDNS(serverList->servers[serverList->currServer], 1, rRecord);
					bool found = false;
					if(numAnswers > 0){
						for(int idx=0;idx<numAnswers;idx++){
							if(rRecord[idx].TYPE == 1){
								serverList->servers[serverList->currServer] = rRecord[idx].RDATA;
								found = true;
								break;
							}
						}
					}
					if(!found){serverList->currServer++;continue;}
		 		}
 				break;
 			}
 		}
 		//if we reach the end of the list reset current server to first in list and start
 		//using only non IPv4 formatservers by querying their IPv4 addresses
 		if(serverList->currServer >= serverList->numServers){
 			if(!firstTry){return 0;}
   	 		serverList->currServer = 0;
   	 		firstTry = false;
   	 		continue;
 		}
		
		server = serverList->servers[serverList->currServer];
		
    	/* **********open UDP socket with DNS Host	****************/
		memset(&hints, 0, sizeof hints);
		hints.ai_family = AF_UNSPEC;// set to AF_INET to force IPv4
		hints.ai_socktype = SOCK_DGRAM;
		//getaddrinfo() gets information about a host name and/or 
		//service and load up a struct sockaddr with the result.
		if ((rv = getaddrinfo(server, port, &hints, &servinfo)) != 0) {
    		fprintf(stderr, "getaddrinfo: %s\n", gai_strerror(rv));
    		return -1;
		}

		// loop through all the results and make a socket
		for(p = servinfo; p != NULL; p = p->ai_next) {
			//if socket() didn't return socket description. or -1 => error
    		if ((sockfd = socket(p->ai_family, p->ai_socktype,
            		p->ai_protocol)) == -1) {
        			perror("talker: socket");
        			continue;
    		}

    		break;
    	}
    	if (p == NULL) { //failing to bind socket
        	fprintf(stderr, "talker: failed to bind socket\n");
        	return -1;
		}
	
	
		/******************SEND the message to the server ******************/
	
    	if ((numbytes = sendto(sockfd, byteArray, rrsigSize, 0,
             p->ai_addr, p->ai_addrlen)) == -1) {
        	perror("talker: sendto");
        	exit(1);
    	}
    	else {
    		if(debug)printf("Sent %d bytes to server %s:%s via UDP\n",numbytes, server,port);
    	}
    
		/* Call select() */
		int result;
		bool timeout = true;
		byte responseMessage[4100];
		int totalResponse = 0;

		do {
		   FD_ZERO(&readset);
		   FD_SET(sockfd, &readset);
		   result = select(sockfd + 1, &readset, NULL, NULL, &tv);
		} while (result == -1 && errno == EINTR);


		if (result > 0) {
		   if(FD_ISSET(sockfd, &readset)) {
			/* The socket_fd has data available to be read */
			result = recvfrom(sockfd, responseMessage+totalResponse, 4100-totalResponse, 0,
		   		 			   p->ai_addr, &p->ai_addrlen);
			totalResponse += result;
			  if (result == 0) {
				 /* This means the other side closed the socket */
				 printf("DNS socket was closed on server side");
			  }
			  else if(result == -1){
			  	perror("Client: recv(): ");	
			  	close(sockfd);
			  	exit(1);
			  }
			  timeout = false;
		   }
		   
		   
		   /** **************************  Handle the response message ****************/
		   if(totalResponse > 0){
			int numAnswers = parseResponseMessage(responseMessage, messageSize, serverList, currKnown, hostname, rRecord);
			if(numAnswers > 0){
				freeaddrinfo(p);
				close(sockfd);
				return numAnswers;
			}
			else if(numAnswers == 0){
				if(debug)printf("Answer not found, trying next server\n");
				serverList->currServer++;
			}
			else{
				if(debug){
					printf("Server list updated!\n");
					for(int i=0;i<serverList->numServers;i++)					
						printf("%s\n",serverList->servers[i]);
				}
				serverList->currServer = 0;
				firstTry = true;
			}
		   }
		}
		else if (result < 0) {
		   /* An error ocurred, just print it to stdout */
		   printf("Error on select(): %s", strerror(errno));
		   close(sockfd);
		   exit(1);
		}
    
    	freeaddrinfo(p);
    	close(sockfd);
	}//end Big While Loop
    
	return 0;
}

/**queries all the servers in the serverList with the question message and retrieves the answer
	if the answer was found return the number of answers found, return 0 if no answer was found, and return -1 if the server
	list was updated*/
int parseResponseMessage(byte * responseMessage, int offset, ServerList * serverList, char * currKnown, char * hostname, ResourceRecord *answerRecord){
	if(printResponseByteArray){
		for(int i=0;i<500;i++){
			if(i%10 == 0)printf("\n");
			printf("%#x\t",responseMessage[i]);
		}
		printf("\n");
	}
	//check if the RCODE is set
	if((int)(responseMessage[3] & 0x0f) > 0){
		printf("There was an error in the response message: %d\n",(int)(responseMessage[3] & 0x0f));
		return 0;
	}
	
	unsigned short numQuestion, numAnswer, numAuthority, numAdditional;
	numQuestion = ((responseMessage[4]<<8) & 0xFF00) + (responseMessage[5] & 0x00FF);
	numAnswer = ((responseMessage[6]<<8) & 0xFF00) + (responseMessage[7] & 0x00FF);
	numAuthority = ((responseMessage[8]<<8) & 0xFF00) + (responseMessage[9] & 0x00FF);
	numAdditional = ((responseMessage[10]<<8) & 0xFF00) + (responseMessage[11] & 0x00FF);
	//printf("there was %d answers, %d authorities, %d additional\n",numAnswer, numAuthority, numAdditional);
	
	//WHAT DO WE DO IF NUMBER OF QUESTIONS > 1? CAN THIS EVER HAPPEN?
	if(numQuestion > 1){printf("Number of Questions was > 1, ignoring?!!\n");return 0;}
	
	ResourceRecord additional[numAdditional];
	ResourceRecord authority[numAuthority];
	
	if(numAnswer > 0){
		for(int i=0;i<numAnswer;i++){
			offset = parseResourceRecord(responseMessage, offset, &answerRecord[i]);
		}
		return numAnswer;
	}
	else{
//printf("here offset is %d\n", offset); //*****************************************************************************
		for(int i=0;i<numAuthority;i++){
			if(nameDebug)printf("parse Authority RR %d at offset %d\n", i, offset);
			offset = parseResourceRecord(responseMessage, offset, &authority[i]);
			//if this was an SOA record return the Answer as not found
			if(authority[i].TYPE == 6){
				answerRecord[0] = authority[i];
				return 1;
			}
		}

		for(int i=0;i<numAdditional;i++){
			if(nameDebug)printf("parse Additional RR %d at offset %d\n", i, offset);
			offset = parseResourceRecord(responseMessage, offset, &additional[i]);
		}
		//printf("AUTHORITY SECTION:\n");
		//printRRList(authority, numAuthority);
		//printf("ADDITIONAL SECTION\n");
		//printRRList(additional, numAdditional);
		int num = compareBestKnown(currKnown, hostname, authority, numAuthority);
		if(num){
			numAuthority = num;
			updateServerList(serverList, authority, numAuthority, additional, numAdditional);
			return -1;
		}
	}
	return 0;
}

/** parses the resource record for all values and returns the offset of the byte after the end
	of the resource recrod in the responseMessage */
int parseResourceRecord(byte * responseMessage, int offset, ResourceRecord  * rRecord){	
	//check if the begining is a pointer to the name or a label and put the offset after the pointer/label
	if(nameDebug)
		printf("OFFSET STARTS at %#X\n",offset + 0x2A);
	offset = parseName(responseMessage, offset, rRecord, 'n', NULL);		
	if(nameDebug)
		printf("Name ends at %#X\n",offset + 0x2A);
	
	rRecord->TYPE = ((responseMessage[offset]<<8) & 0xFF00) + (responseMessage[offset+1] & 0x00FF);
	offset +=2;
	rRecord->CLASS = ((responseMessage[offset]<<8) & 0xFF00) + (responseMessage[offset+1] & 0x00FF);
	offset +=2;
	rRecord->TTL = ((responseMessage[offset]<<24) & 0xFF000000) + ((responseMessage[offset+1]<<16) & 0x00FF0000) +
				   ((responseMessage[offset+2]<<8) & 0x0000FF00) + (responseMessage[offset+3] & 0x000000FF);
	offset += 4;
	rRecord->RDLENGTH = ((responseMessage[offset]<<8) & 0xFF00) + (responseMessage[offset+1] & 0x00FF);

	int tempOff = offset+2;
	offset += rRecord->RDLENGTH + 2;
	
	if(nameDebug)printf("rdl: %d, offset %#X\n",rRecord->RDLENGTH, offset + 0x2A);

	//if the type is A, parse the IPv4 address into RDATA
	if(rRecord->TYPE == 1){
		char *buf = new char[20];
		sprintf(buf, "%u.%u.%u.%u", 0x000000FF & responseMessage[tempOff], 0x000000FF & responseMessage[tempOff+1], 
								    0x000000FF & responseMessage[tempOff+2], 0x000000FF & responseMessage[tempOff+3]);
		rRecord->RDATA = &(*buf);
	}//if the type is NS SOA, CNAME or MX, parse the name into RDATA
	else if (rRecord->TYPE == 2 || rRecord->TYPE == 15 || rRecord->TYPE == 5 || rRecord->TYPE == 6){
		if(rRecord->TYPE == 15){
			rRecord->PREFERENCE = (0xFF00 & responseMessage[tempOff]<<8) + ( 0x00FF & responseMessage[tempOff+1]); 
			tempOff += 2;//offset 2 for the PREFERENCE field
		}
		//Put the RDATA as MNAME(source of data) or RNAME(The Mailbox of person responsible)
		/*if(rRecord->TYPE == 6){
			tempOff = parseName(responseMessage, tempOff, rRecord, 'd');
		}*/
		parseName(responseMessage, tempOff, rRecord, 'd', NULL);
	}
	else if(rRecord->TYPE == 46){
		RRSIG_Record * sigRecord = new RRSIG_Record();
		parseRRSIG(responseMessage, tempOff, sigRecord, rRecord->RDLENGTH);
		rRecord->RRSIG = sigRecord;
	}
	if(nameDebug)printf("END offset  %#X\n",0x2A + offset);
	return offset;
}

/** parses the name label from the given offset in the message. type n sets rRecord->Name, type d sets rRecord->RDATA
	returns the offset in the message right after the end of the name label*/
int parseName(byte * responseMessage, int offset, ResourceRecord * rRecord, char type, char *theName){
	char * nameArray = new char[255];
	int numLetters;
	int nameOffset=offset;
	int index = 0;
	bool hadPointer = false;
	bool firstWasPointer = false;
	while(responseMessage[nameOffset] != 0){
		if(nameDebug)printf("current offset %d = %#x\n", nameOffset, responseMessage[nameOffset]);
		//the the name is a pointer
		if((0xC0 & responseMessage[nameOffset]) == 0xC0){
			//if this pointer was the start of the Name then increment offset by and return this value at the end
			if(nameOffset == offset && !firstWasPointer){firstWasPointer = true; offset += 2;}
			
			//if the first part wasn't a pointer and this is the first pointer then increment offset and return 
			//this value at the end
			if(!firstWasPointer && !hadPointer){offset += 2;}
			
			nameOffset = (0x3F00 & responseMessage[nameOffset]<<8) + (0x00FF & responseMessage[nameOffset+1]);
			if(nameDebug)printf("pointer to %d\n",nameOffset);
			hadPointer = true;
		}
		
		numLetters = responseMessage[nameOffset++];
		//if the Name has not had a pointer always increment the offset
		if(!hadPointer){
			if(nameDebug)printf("label at %d\n",nameOffset);
			offset += numLetters +1;
		}
		
		if(nameDebug)printf("grabbing %d letters\n", numLetters);
		for(int i=0;i<numLetters;i++){
			nameArray[index++] = responseMessage[nameOffset++];
		}
		nameArray[index++] = '.';
	}
	nameArray[index] = '\0';
	if(!hadPointer)offset++;
	
	if(type == 'n')
		rRecord->Name = nameArray;
	else if(type == 'd')
		rRecord->RDATA = nameArray;
	else if(type == 't'){
		unsigned int i;
		for(i=0;i<strlen(nameArray);i++)
			theName[i] = nameArray[i];
		theName[i] = '\0';
	}
		
	return offset;
}

void parseRRSIG(byte * responseMessage, int offset, RRSIG_Record *rrsig, int totalSize){
	int origOffset = offset;
	rrsig->Type = ((responseMessage[offset]<<8) & 0xFF00) + (responseMessage[offset+1] & 0x00FF);
	offset +=2;
	rrsig->algorithm = responseMessage[offset++];
	rrsig->labels = responseMessage[offset++];
	rrsig->Orig_TTL = ((responseMessage[offset]<<24) & 0xFF000000) + ((responseMessage[offset+1]<<16) & 0x00FF0000) +
				  	  ((responseMessage[offset+2]<<8) & 0x0000FF00) + (responseMessage[offset+3] & 0x000000FF);
	offset+=4;
	rrsig->sig_Expiration = ((responseMessage[offset]<<24) & 0xFF000000) + ((responseMessage[offset+1]<<16) & 0x00FF0000) +
				  	  ((responseMessage[offset+2]<<8) & 0x0000FF00) + (responseMessage[offset+3] & 0x000000FF);
	offset += 4;
	rrsig->sig_Inception = ((responseMessage[offset]<<24) & 0xFF000000) + ((responseMessage[offset+1]<<16) & 0x00FF0000) +
				  	  ((responseMessage[offset+2]<<8) & 0x0000FF00) + (responseMessage[offset+3] & 0x000000FF);
	offset += 4;
	rrsig->keytag = ((responseMessage[offset]<<8) & 0xFF00) + (responseMessage[offset+1] & 0x00FF);
	//rrsig->keytag = ntohs(rrsig->keytag);
	offset +=2;
	char * name = new char[256];
	offset = parseName(responseMessage, offset, NULL, 't',name);
	rrsig->signature = name;
	
	int calcLength = totalSize - (offset - origOffset);
	unsigned char * sigCalc = new unsigned char[1000];
	
	for(int i=0;i<calcLength;i++){
		if(i%3 == 0)
			sigCalc[i] = (0x3F & responseMessage[i]>>2);
		else if(i%3 == 1)
			sigCalc[i] = (0x30 & responseMessage[i-1]<<4) + (0x0F & responseMessage[i]>>4);
		else if(i%3 == 2){
			sigCalc[i] = (0x3C & responseMessage[i-1]<<2) + (0x03 & responseMessage[i]>>6);
			sigCalc[i] = (0x3F & responseMessage[i]);
		}
	}
	
	for(int i=0;i<calcLength;i++){
		if((unsigned int)sigCalc[i] < 26){
			sigCalc[i] += 65;
		}
		else if((unsigned int)sigCalc[i] < 52){
			sigCalc[i] += 71;
		}
		else if((unsigned int)sigCalc[i] < 62){
			sigCalc[i] -= 4;
		}
		else if((unsigned int)sigCalc[i] == 62){
			sigCalc[i] = 43;
		}
		else{
			sigCalc[i] = 47;
		}
	}
	sigCalc[calcLength] = '\0';
	rrsig->sigCalc = (char *)sigCalc;
}


/** compares the currently best closest match of servers to our host, with the current authority
	list of servers.  If the new list is better, than use the new list, otherwise use the old serverList.
	returns the number of authorities with better matches. returning 0 means the old list was better.*/
int compareBestKnown(char * currKnown, char *hostname, ResourceRecord * authority, int numAuthority){
	bool newList =false;
	toLowerCase(hostname);
	toLowerCase(currKnown);
	for(int i=0;i<numAuthority;i++){
		//if it is not a NS, CNAME, or A then ignore it
		if(authority[i].TYPE != 1 && authority[i].TYPE != 2 && authority[i].TYPE != 5){
			shiftLeft(authority, numAuthority, i);
			i--;
			numAuthority--;
			continue;
		}
		toLowerCase(authority[i].Name);
		if(strcmp(currKnown, authority[i].Name) == 0){
			if(!newList){
				shiftLeft(authority, numAuthority, i);
				i--;
				numAuthority--;
			}
		}
		else if(strlen(currKnown) > strlen(authority[i].Name)){
			if(newList){
				shiftLeft(authority, numAuthority, i);
				i--;
				numAuthority--;
			}
		}
		else {
			unsigned int index = 0;
			bool match = false;
			while(index < strlen(hostname)){
				if(authority[i].Name[0] == hostname[index]){
					match = true;
					for(unsigned int j=0;j<strlen(authority[i].Name)-1;j++){
						if(authority[i].Name[j] != hostname[index+j]){
							match= false;
							break;
						}
					}
					if(match) break;
				}
				index++;
			}
			
			if(match){
				if(newList == false){
					for(int j=0;j<i;j++){
						shiftLeft(authority, numAuthority, j);
						i--;
						numAuthority--;
					}
				}
				newList = true;
				unsigned int j;
				for(j=0;j<strlen(authority[i].Name);j++)
					currKnown[j] = authority[i].Name[j];
				currKnown[j] = '\0';
			}
		}
	}
	if(newList)return numAuthority;
	return 0;
}


void shiftLeft(ResourceRecord * rList, int numList, int offset){
	for(int i=0;i<numList-1;i++){
		rList[offset].Name = rList[offset+1].Name;
		rList[offset].TYPE = rList[offset+1].TYPE;
		rList[offset].CLASS = rList[offset+1].CLASS;
		rList[offset].RDLENGTH = rList[offset+1].RDLENGTH;
		rList[offset].RDATA = rList[offset+1].RDATA;
		rList[offset].PREFERENCE = rList[offset+1].PREFERENCE;
		rList[offset].TTL = rList[offset+1].TTL;
	}
}

//Free all the memory of the servers and maek a new serverList using authority and additional list mapping
void updateServerList(ServerList * serverList, ResourceRecord * authority,int numAuth, ResourceRecord *additional, int numAdd){
	//free memory of servers
	for(int i=0;i<serverList->numServers;i++)delete serverList->servers[i];
	serverList->servers = (char**)calloc(numAuth,256);

	//associate the authority RDATA with the additional RDATA
	//if no association, we must query for the A type RR to find the IP address.
	bool found = false;
	int index;
	int totalNew = numAuth;
	for(int i=0;i<numAuth;i++){
		if(authority[i].TYPE != 1 && authority[i].TYPE != 2){totalNew--;continue;}
		found = false;
		for(index=0;index<numAdd;index++){
			if(strcmp(authority[i].RDATA, additional[index].Name) == 0){
				if(additional[index].TYPE == 1){//check that this is an IPv4 address
					found = true;
					break;
				}
			}
		}

		if(found){
			serverList->isIPFormat[i] = true;
			serverList->servers[i] = additional[index].RDATA;
		}
		else{
			serverList->isIPFormat[i] = false;
			serverList->servers[i] = authority[i].RDATA;
		}
	}
	
	serverList->numServers = totalNew;
}

void lookupZoneInfo(char * hostname){
	ResourceRecord * rRecord = new ResourceRecord[20];
	//Qtype 15 == MX
	int numAnswers = queryDNS(hostname, 15, rRecord);
	if(numAnswers > 0){
		if(rRecord[0].TYPE == 6)
			printf("SOA Record reported. There was no MX for %s\n",hostname);
		else
			//printf("ANSWER SECTION:%d\n", numAnswers);
		printRRList(rRecord, numAnswers);
	}
	else{
		printf("There was no answer for the MX of %s\n",hostname);
	}

}

//Returns an array of strings corresponding to the DNS servers
//DNS servers are written to a file named 'dns'
void getDNSServers(ServerList * sl){
	char command[] = "dig | cut -f 5 | egrep '^[[:digit:]]{1,3}\\.[[:digit:]]{1,3}\\.[[:digit:]]{1,3}\\.[[:digit:]]{1,3}' > dns";
	system(command);
	//Parse each line in the file and put each of the lines in an array
	FILE *dnslistfile;
	dnslistfile = fopen("dns", "r");
	if (dnslistfile==NULL){
		perror ("Error opening file");
		return;
	}
	char c;
	int lines = 0;
	while((c = fgetc(dnslistfile)) != EOF){
		if(c == '\n'){
		  lines++; 
		}
	}

	sl->servers = (char**)calloc(lines,100);
	sl->numServers = lines;
	rewind(dnslistfile);

	int linepos = 0;
	char * server;
	int index;
	while(!feof(dnslistfile)){
		server = (char *)malloc(100);	
		fgets(server,100,dnslistfile);//Hopefully there is never more than 100 characters on a line
		index = 0;
	
		while(server[index] != '\n')index++;
		server[index] = '\0';
		if(server != NULL){
			sl->servers[linepos] = &(*server);
			sl->isIPFormat[linepos] = true;
		}
		linepos++;
		if(linepos >= lines)break;
	}
	fclose(dnslistfile);
}

void printRRList(ResourceRecord * rRecord, int size){
	char classValue[5][3] = {"NA","IN","CS","CH","HS"};
	char typeValue[19][6] = {"UKNWN","A","NS","MD","MF","CNAME","SOA","MB","MG","MR","NULL","WKS","PTR","HINFO","MINFO","MX","TXT","AAAA", "RRSIG"};
	for(int i=0;i<size;i++){

		//verify that type is one of the above typeValue[]'s, otherwise set to unknown
		int type = rRecord[i].TYPE;
		if(type > 16){
			if(type == 28)
				type = 17;
			else if(type == 46)
				type = 18;
			else
				type = 0;
		}
		
		if(type == 1 || type == 2 || type == 5 || type == 6 || type == 15 || type == 18)
			printf("%s\t%d\t%s\t%s\t",
			 rRecord[i].Name, rRecord[i].TTL, classValue[rRecord[i].CLASS], typeValue[type]); 
		//NS, A, CNAME RR's
		if(rRecord[i].TYPE == 2 || rRecord[i].TYPE == 1 || rRecord[i].TYPE == 5 || rRecord[i].TYPE == 6){
			printf("%s\n", rRecord[i].RDATA);
		}//MX RR
		else if(rRecord[i].TYPE == 15){
			printf("%d  %s\n", rRecord[i].PREFERENCE, rRecord[i].RDATA);
		}//RRSIG RR
		else if(rRecord[i].TYPE == 46){
			int t = rRecord[i].RRSIG->Type;
			if(t > 16){
				 if(t == 46)
				 	t = 18;
				 else 
					t = 0;
			}
				 
			printf("%s %d %d %d %d %d %d %s\n", 
			typeValue[t], rRecord[i].RRSIG->algorithm, rRecord[i].RRSIG->labels, rRecord[i].RRSIG->Orig_TTL,
			rRecord[i].RRSIG->sig_Expiration, rRecord[i].RRSIG->sig_Inception, rRecord[i].RRSIG->keytag, rRecord[i].RRSIG->signature);
			for(unsigned int j=0;j<strlen(rRecord[i].RRSIG->sigCalc);j++){
				if(j%50 == 49)
					printf("\n");
				printf("%c",rRecord[i].RRSIG->sigCalc[j]);
			}
			printf("\n");
		}//Ignore everything else
		//else printf("IGNORED\n");
	}
}

void toLowerCase(char * string){
	for(unsigned int i=0;i<strlen(string);i++){
		//if ascii is A...Z
		if(string[i] >= 65 && string[i] <= 90)
			string[i] +=32;
	}
}

int main(int argc, char *argv[])
{
	if(argc != 2){
		printf("Format is ./myresolver zonename");
		exit(1);
	}
	
	char * hostname = argv[1];
	toLowerCase(hostname);
	lookupZoneInfo(hostname);

    return 0;
}
